using System;
using System.Collections.Generic;
using System.Linq;
using NUnit.Framework;
using ProjectEuler.Core.Helpers;

namespace ProjectEuler.Core
{
    public class Problem64 : IProjectEulerProblem
    {
        public int Number
        {
            get { return 64; }
        }

        public string Description
        {
            get { return "How many continued fractions for N <= 10000 have an odd period?"; }
        }

        public string Answer
        {
            get { return NumberOfOddPeriods(10000).ToString(); }
        }

        protected int NumberOfOddPeriods(int n)
        {
            var odds = 0;
            for(int i =2;i<=n;i++)
            {
                if(IsIrrationalRoot(i))
                {
                    var fraction = ContinuedFractionForIrrationalSquareRootOf(i);
                    if(MathHelper.IsEven(fraction.Count))
                    {
                        // checking 'even' since the first number will not be part of the repeating sequence
                        odds++;
                    }
                }
            }
            return odds;
        }

        protected static bool IsIrrationalRoot(int i)
        {
            var root = Math.Sqrt(i);
            var rootFloor = (long) Math.Floor(root);
            var rootFloorSquared = (long) Math.Pow(rootFloor, 2);
            return rootFloorSquared != i;
        }

        // this algorithm is taken from the "Continued fraction expansion"
        // at Wikipedia: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion
        // hence the short variable names
        protected List<long> ContinuedFractionForIrrationalSquareRootOf(long S)
        {
            var m = new Dictionary<long, long> {{0, 0}};
            var d = new Dictionary<long, long> {{0, 1}};
            var a = new Dictionary<long, long> {{0, (long) Math.Floor(Math.Sqrt(S))}};

            int n = 0;
            while (true)
            {
                m[n + 1] = (d[n]*a[n]) - m[n];
                d[n + 1] = (S - (long) Math.Pow(m[n + 1], 2))/d[n];
                a[n + 1] = (long) Math.Floor((Math.Sqrt(S) + m[n + 1])/d[n + 1]);
                n++;
                if (IsTripletSameAsAPreviousTriplet(m, d, a, n)) break;
            }

            return a
                .Where(kvp => kvp.Key != n)
                .OrderBy(kvp => kvp.Key)
                .Select(kvp => kvp.Value)
                .ToList();
        }

        protected static bool IsTripletSameAsAPreviousTriplet(Dictionary<long, long> m, Dictionary<long, long> d, Dictionary<long, long> a, int n)
        {
            for(int i=0;i<n;i++)
            {
                if(m[i] == m[n] && d[i]==d[n] && a[i] == a[n])
                {
                    return true;
                }
            }
            return false;
        }
    }

    [TestFixture]
    public class Problem64Tests : Problem64
    {
        [Test]
        public void Can_get_continued_fraction_for_square_roots()
        {
            Assert.That(ContinuedFractionForIrrationalSquareRootOf(2), Is.EquivalentTo(new List<long> {1, 2}));
            Assert.That(ContinuedFractionForIrrationalSquareRootOf(3), Is.EquivalentTo(new List<long> {1, 1, 2}));
            Assert.That(ContinuedFractionForIrrationalSquareRootOf(5), Is.EquivalentTo(new List<long> {2, 4}));
            Assert.That(ContinuedFractionForIrrationalSquareRootOf(6), Is.EquivalentTo(new List<long> {2, 2, 4}));
            Assert.That(ContinuedFractionForIrrationalSquareRootOf(7), Is.EquivalentTo(new List<long> {2, 1, 1, 1, 4}));
            Assert.That(ContinuedFractionForIrrationalSquareRootOf(8), Is.EquivalentTo(new List<long> {2, 1, 4}));
            Assert.That(ContinuedFractionForIrrationalSquareRootOf(10), Is.EquivalentTo(new List<long> {3, 6}));
            Assert.That(ContinuedFractionForIrrationalSquareRootOf(11), Is.EquivalentTo(new List<long> {3, 3, 6}));
            Assert.That(ContinuedFractionForIrrationalSquareRootOf(12), Is.EquivalentTo(new List<long> {3, 2, 6}));
            Assert.That(ContinuedFractionForIrrationalSquareRootOf(13), Is.EquivalentTo(new List<long> {3, 1, 1, 1, 1, 6}));

            Assert.That(ContinuedFractionForIrrationalSquareRootOf(23), Is.EquivalentTo(new List<long> {4, 1, 3, 1, 8}));
        }

        [Test]
        public void Can_find_irrational_roots()
        {
            Assert.That(IsIrrationalRoot(2));
            Assert.That(IsIrrationalRoot(3));
            Assert.That(IsIrrationalRoot(5));
            Assert.That(IsIrrationalRoot(6));
            Assert.That(IsIrrationalRoot(7));
            Assert.That(IsIrrationalRoot(8));
            Assert.That(IsIrrationalRoot(10));
            Assert.That(IsIrrationalRoot(11));
            Assert.That(IsIrrationalRoot(12));
            Assert.That(IsIrrationalRoot(13));

            Assert.That(!IsIrrationalRoot(9));
            Assert.That(!IsIrrationalRoot(16));
            Assert.That(!IsIrrationalRoot(25));
        }

        [Test]
        public void Can_find_previous_matching_triplet()
        {
            var m = new Dictionary<long, long> { { 0, 0 } };
            var d = new Dictionary<long, long> { { 0, 1 } };
            var a = new Dictionary<long, long> { { 0, 9 } };
            m[1] = 5;
            d[1] = 5;
            a[1] = 5;
            m[2] = 5;
            d[2] = 5;
            a[2] = 5;
            Assert.That(IsTripletSameAsAPreviousTriplet(m, d, a, 2));

            m[2] = 55;
            Assert.That(!IsTripletSameAsAPreviousTriplet(m, d, a, 2));
        }
    }
}